package 力扣_链表.面试常考;


import java.util.ArrayDeque;
import java.util.Deque;

/**优先使用迭代、递归、栈
 * @author zx
 * @create 2022-08-12 18:03
 */
public class 反转链表_206 {
    /**
     * @return 迭代
     */
    public ListNode reverseList3(ListNode head){
        ListNode prev = null;
        while(head != null){
            //暂存一下当前处理节点的后面
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

    /**
     * @return 栈
     */
    public ListNode reverseList2(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode dummyHead = new ListNode(5001);
        ListNode temp = dummyHead;
        while(!stack.isEmpty()){
            temp.next = stack.pop();
            temp = temp.next;
        }
        temp.next = null;
        return dummyHead.next;
    }

    /**
     * @return 递归()
     */
    public ListNode reverseList(ListNode head) {
        //递归
        //递归出口
        if (head == null || head.next == null) {
            return head;
        }
        //暂存一下当前处理节点的后面
        ListNode node = head.next;
        //子函数的作用：反转第二个节点之后的子链表
        ListNode newHead = reverseList(node);
        //3.将node.next = head;
        //head.next = null;
        node.next = head;
        head.next = null;
        return newHead;
    }
    /**
     * @return 头插法
     */
    public ListNode reverseList1(ListNode head) {
        //头插法：会有额外的空间开辟(空间复杂度O(n))
        if(head == null || head.next == null){
            return head;
        }
        //新链表的虚拟头节点
        ListNode dummyHead = new ListNode(5001);
        while(head != null){
            ListNode node = new ListNode(head.val);
            //把当前节点插到原先链表的头
            node.next = dummyHead.next;
            //更新为当前最新的头节点
            dummyHead.next = node;
            head = head.next;
        }
        return dummyHead.next;
    }
}
